package gdut.edu.demo04;

import java.util.Arrays;

/**
 * @Description
 * @Author JiaFu 直接插入排序
 * @Date 2022/11/10 16:19
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3,1,0,9,2,22};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        //遍历所有的数字
        for (int i = 1; i < arr.length; i++) {
            //如果当前数字比前面的数字小
            if (arr[i] < arr[i - 1]) {
                //取出当前数字作为临时变量
                int temp = arr[i];
                //遍历当前数字前面的所有数字
                int j ;
                for (j = i-1; j >= 0; j--) {
                    if (arr[j] > temp ) {
                        //如果前面的数字大于临时变量，全部往后移动一位
                        arr[j + 1] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j+1] = temp;
            }
        }
    }
}
